package Review.Linklist;

public class Test1 {

    public static void main(String[] args) {


    }
  public MyListNode.ListNode reserve(MyListNode.ListNode head) {
      MyListNode.ListNode prev=null;
      MyListNode.ListNode curr=head;
        //用于记录后续的节点
      MyListNode.ListNode temp=null;
        while(curr!=null){
            //记录
            temp=curr.next;
            curr.next=prev;
            //进行后移
            prev=curr;
            curr=temp;
        }
        return prev;
  }
  public MyListNode.ListNode reserve2(MyListNode.ListNode head) {
        return reserve3(null,head);
  }
  public MyListNode.ListNode reserve3(MyListNode.ListNode pre, MyListNode.ListNode cur) {
        if(cur==null){
            return pre;
        }
        MyListNode.ListNode temp = cur.next;
        cur.next=pre;
        //实现身份后移
        return reserve3(cur,temp);
  }
  //两两交换版本
    public MyListNode.ListNode swapPairs(MyListNode.ListNode head) {
        //终止条件
        if(head==null||head.next==null){
            return head;
        }
        MyListNode.ListNode next=head.next;
        //返回下次递归前面的那个节点
        MyListNode.ListNode newNode=swapPairs(next.next);
        next.next=head;
        head.next=newNode;
        return next;
    }
    public MyListNode.ListNode swapPairs2(MyListNode.ListNode head) {
        //虚拟节点
        MyListNode.ListNode dumyhead=new MyListNode.ListNode(-1);
        dumyhead.next=head;
        MyListNode.ListNode cur=dumyhead;
        //保存后续的值
        MyListNode.ListNode temp;
        MyListNode.ListNode first;
        MyListNode.ListNode second;
        while(cur.next!=null&&cur.next.next!=null){
            //防止后续的值丢失
            temp=cur.next.next.next;
            first=cur.next;
            second=cur.next.next;
            cur.next=second;
            second.next=first;
            first.next=temp;
        }
        return dumyhead.next;
    }
    public MyListNode.ListNode removeElement(MyListNode.ListNode head,int n) {
        MyListNode.ListNode dumyhead=new MyListNode.ListNode(-1);
        dumyhead.next=head;
        MyListNode.ListNode first=dumyhead;
        MyListNode.ListNode second=dumyhead;
        for(int i=0;i<=n;i++){
            first=first.next;
        }
        while(first!=null){
            first=first.next;
            second=second.next;
        }
        if(second.next!=null){
            //把second的下一个删除
            second.next=second.next.next;
        }
        return dumyhead.next;
    }

}
